# 给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 
# 
#  找到所有在 [1, n] 范围之间没有出现在数组中的数字。 
# 
#  您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。 
# 
#  示例: 
# 
#  
# 输入:
# [4,3,2,7,8,2,3,1]
# 
# 输出:
# [5,6]
#  
#  Related Topics 数组 
#  👍 720 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            x = (num - 1) % n
            nums[x] += n
        return [i + 1 for i, num in enumerate(nums) if nums[i] <= n]


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 数学题, 数字大小都在数组长度范围内, 故可以根据数字大小取数组中的位置, 增加数组长度
# 如果有的数字, 对应位置增加后大于数组长度, 故数组中不大于的位置, 即为缺的数字
# 位置的数字可能已被加大, 还原数字, 避免越界
# 数字 + n 之后还原  x+n % n 等于 x
#     def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
#         n = len(nums)
#         for num in nums:
#             x = (num - 1) % n
#             nums[x] += n
#         return [i + 1 for i, num in enumerate(nums) if num <= n]

if __name__ == '__main__':
    s = Solution()
    a = [4, 3, 2, 7, 8, 2, 3, 1]
    result = s.findDisappearedNumbers(a)
    # [5,6]
    log(result)
    b = [1, 1]
    s.findDisappearedNumbers(b)
